package com.rayboo.example.algorithm.sort;

import com.rayboo.example.util.ArrayUtils;

import java.util.Arrays;

/**
 * 希尔排序
 *
 * @author ray
 * @since 2019/08/01
 *
 * <p>希尔(Shell)排序又称为缩小增量排序，它是一种插入排序。它是直接插入排序算法的一种威力加强版。
 *
 * <p>希尔排序的基本思想是：把记录按步长 gap 分组，对每组记录采用直接插入排序方法进行排序。
 * 随着步长逐渐减小，所分成的组包含的记录越来越多，当步长的值减小到 1 时，整个数据合成为一组，构成一组有序记录，则完成排序。
 *
 * <p>https://mp.weixin.qq.com/s/dyRTXwsmUmFcF9PeFR8OrQ
 * <p>https://www.runoob.com/w3cnote/shell-sort.html
 */
public class ShellSort {

    public static void main(String[] args) {
        int[] arr = ArrayUtils.randomNoRepeatIntArray(0, 100, 10);
        System.out.println("排序前：\n" + Arrays.toString(arr));

        shellSort(arr);
        System.out.println("排序后：\n" + Arrays.toString(arr));

        System.out.println("=====================================");

        int[] array = ArrayUtils.randomNoRepeatIntArray(0, 10, 5);
        System.out.println("排序前：\n" + Arrays.toString(array));

        new ShellSort().sort(array);
        System.out.println("排序后：\n" + Arrays.toString(array));
    }

    /**
     * 希尔排序
     *
     * @param arr 数组
     */
    public static void shellSort(int[] arr) {
        int j, temp;
        int gap = arr.length / 2;

        while (1 <= gap) {
            // 把距离为 gap 的元素编为一个组，扫描所有组
            for (int i = gap; i < arr.length; i++) {
                temp = arr[i];

                // 对距离为 gap 的元素组进行排序
                for (j = i - gap; j >= 0 && temp < arr[j]; j = j - gap) {
                    arr[j + gap] = arr[j];
                }
                arr[j + gap] = temp;
            }

            gap = gap / 2; // 减小增量
        }
    }

    /**
     * 希尔排序 （使用while）
     *
     * @param arr 数组
     */
    public int[] sort(int[] arr) {
        int i, j, temp;
        int gap = arr.length / 2;

        while (gap >= 1) {
            // 把距离为 gap 的元素编为一个组，扫描所有组
            for (i = gap; i < arr.length; i++) {
                temp = arr[i];
                j = i - gap;

                //需要注意的是，这里array[j] > temp将会使数组从小到到排序。
                while (j >= 0 && arr[j] > temp) {
                    arr[j + gap] = arr[j];
                    j = j - gap;
                }
                arr[j + gap] = temp;
            }

            gap = gap / 2;
        }

        return arr;
    }
}
